The present disclosure relates to a bus system. More particularly, the present disclosure relates to a deadlock avoidance circuit employed in an interconnect of the bus system.
In a bus system, connected apparatus are linked to a bus (also referred to as an interconnect) and data is transferred among the connected apparatus. The connected apparatus playing a leading role in a transfer of data between two apparatus is referred to as a master whereas the other connected apparatus operating as a passive apparatus is referred to as a slave. Typically, a processor is assumed to be the connected apparatus referred to as a master whereas a memory is assumed to be the connected apparatus referred to as a slave.
In such a bus system, a sequence of operations referred to as transactions for transferring data includes a request for a transfer of the data and the actual transfer of the data. By controlling the request for a transfer of data and the actual transfer of the data independently of each other as split transactions, the efficiency of the transfer of the data can be improved. If a master issues transactions having a dependence relation to a plurality of slaves with the same timing for a case in which split transactions are allowed, on the other hand, this could cause a deadlock between a request for a transfer of data and the actual transfer of the data.
Here, let us assume a system in which masters M1 and M2 as well as slaves S1 and S2 are linked to an interconnect. Let the master M1 issue read transactions having a dependence relation to the slave S1 and, then, the slave S2 whereas the master M2 issue read transactions having a dependence relation to the slave S2 and, then, the slave S1.
In this case, the phrase stating “the master M1 issues read transactions having a dependence relation to the slave S1 and, then, the slave S2” implies that the master M1 provides the slaves S1 and S2 with respectively a first read address and a second read address following the first read address and expects to receive first data from the slave S1 and second data following the first data from the slave S2. By the same token, the phrase stating “the master M2 issues read transactions having a dependence relation to the slave S2 and, then, the slave S1” implies that the master M2 provides the slaves S2 and S1 with respectively a third read address and a fourth read address following the third read address and expects to receive third data from the slave S2 and fourth data following the third data from the slave S1.
The read addresses received by the slaves S1 and S2 are expressed as follows:
S1: M11 and M22 
S2: M21 and M12 
In the above expressions of the read addresses, the suffix appended to symbol M1 or M2 indicates whether the read address is an earlier read address from which earlier data will be read out by a slave and received by a master or a later read address from which later data will be read out by the slave and received by the master. For example, the read address M12 is a read address issued by the master M1 in a transaction and the suffix 2 appended to symbol M1 indicates that the master M1 expects to receive later data read out from the read address M12 as a result of the transaction. That is to say, symbols M11 and M12 denote respectively a first read address issued by the master M1 and a second read address issued by the master M1 after the read address M11 and, in this case, the master M1 expects to receive earlier data read out from the read address M11 and later data read out from the read address M12.
In this case, if each slave early outputs the data expected first by a master, no deadlock occurs. If every slave receives transaction read addresses from different masters and is put in a state of not being restricted by any data outputting order whatsoever, on the other hand, the slave may output data to the masters in any order. For the above case in which the slave S1 receives the read addresses M11 and M22 from the masters M1 and M2 respectively whereas the slave S2 receives the read addresses M21 and M12 from the masters M2 and M1 respectively, let us assume for example that the slave S1 makes an attempt to output the data read out from the read address M22 before the data read out from the read address M11 whereas the slave S2 makes an attempt to output the data read out from the read address M12 before the data read out from the read address M21. In this case, the masters M1 and M2 do not accept the pieces of data which the slaves S1 and S2 are trying to output. This is because the master M1 expects the slave S1 to first output the data read out from the read address M11 to the master M1 but it is the slave S2 that makes an attempt to first output the data read out from the read address M12 to the master M1. By the same token, the master M2 expects the slave S2 to first output the data read out from the read address M21 to the master M2 but it is the slave S1 that makes an attempt to first output the data read out from read address M22 to the master M2. As long as the master M1 does not accept the data read out from read address M12 and the master M2 does not accept the data read out from read address M22, the slave S1 cannot output the data read out from read address M11 as expected by the master M1 whereas the slave S2 cannot output the data read out from read address M21 as expected by the master M2. In this way, if a slave outputs pieces of data to a master in a changed order not expected by the master, a deadlock could occur.
In order to solve the deadlock problem described above, there has been proposed a technique for avoiding a deadlock by controlling the reordering of transactions. For example, there has been proposed a data processing apparatus for avoiding a deadlock by making the reordering of transactions impossible through aliasing to replace transaction identifiers with a single identifier. For more information on this data processing apparatus, the reader is advised to refer to documents such as Japanese Patent Laid-open No. 2008-041099 (FIG. 1).